# -*- coding:utf-8 -*-

from base.ListNode import ListNode

"""
 leetcode 23
 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

 归并k个已排序链表，可以分解问题拆解成为，重复k次，归并2个已排序链表，即：
         ListNode l1 = lists.get(0);
         for (int i = 1; i < lists.size(); i++) {
             l1 = mergeTwoLists(l1,lists.get(i));
         }
         return l1;
  但这样总共需要 k 次merge two sorted lists的合并过程，时间复杂度是O(kn),会超出 oj 的时间限制；

  采用分治法，将包含k个链表的列表逐次分成两个部分，再逐次对两个链表合并，这样就有 log(k)次合并过程，
  每次均使用merge two sorted lists的算法。时间复杂度O(nlog(k)


 分治解法
 时间复杂度：O(nlogk) 空间复杂度: O(logk)
"""
class MergeKSortedLists:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        return self.sort(lists,0,len(lists)-1) if lists else None

    def sort(self, lists, lo, hi):
        if lo >= hi:
            return lists[lo]
        mid = (hi-lo)//2 + lo
        l1 = self.sort(lists,lo,mid)
        l2 = self.sort(lists,mid+1,hi)
        return self.mergeTwoLists(l1,l2)

    
    def mergeTwoLists(self,l1,l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if l1 and l2:
            if l1.val > l2.val:
                l2.next = self.mergeTwoLists(l1,l2.next)
                return l2
            else:
                l1.next = self.mergeTwoLists(l1.next,l2)
                return l1
        else:
            return l2 if l2 else l1